package com.sam.book;

/**
 * 求解最大子数组的和
 */
public class MaxSubSum {
    public static void main(String[] args) {
        int[] arr = {1, 3, -6, 7, 2, 456, 32, 3};
        int result;
//        result = force(arr);
//        result = maxSubSum2(arr);
        result = maxSubSum4(arr);
//        result = maxSubRec(arr, 0, arr.length-1);
        System.out.println(result);


    }

    /**
     * 暴力求解
     * @param arr
     * @return
     */
    public static int force(int[] arr) {//O(n^3)
        int maxSum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {//i->j
                int thisSum = 0;
                for(int k=i;k<=j;k++) {
                    thisSum += arr[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 对第一种的优化
     * @param arr
     * @return
     */
    public static int maxSubSum2(int[] arr) {//O(n^2);少一层for
        int maxSum = 0;
        int start = 0, end = 0;
        for (int i = 0; i < arr.length; i++) {
            int thisSum = 0;
            for (int j = i; j < arr.length; j++) {
                thisSum += arr[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                    start = i;
                    end = j;
                }
            }
        }
        System.out.println(start+","+end);
        return maxSum;
    }

    //------递归思想 O(nLog(n))
    public static int maxSubRec(int[] a, int left, int right) {
        if (left == right) {//子序列只有一个数
            return a[left] > 0 ? a[left] : 0;
        }
        int center = (left + right) / 2;
        int maxLeftSum = maxSubRec(a, left, center);
        int maxRightSum = maxSubRec(a, center + 1, right);

        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for (int i = center; i >= left; i--) {
            leftBorderSum += a[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }

        int maxRightBorderSum = 0, rightBorderSum = 0;
        for (int i = center + 1; i <= right; i++) {
            rightBorderSum += a[i];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }

        return Math.max(Math.max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);
    }

    /**
     * 算法4
     * 联机算法：1次扫描，a[i]读入并被处理无需保存，任意时刻 算法对已经读入的数据 给出子系列问题的正确答案
     * 仅需要常量 空间并以纯属时间运行的联机算法几乎是完美的算法
     * @param a
     * @return
     */
    public static int maxSubSum4(int[] a) { //O(n)
        int max = 0;
        int thisSum = 0;
        for (int i = 0; i < a.length; i++) {
            thisSum += a[i];
            if (thisSum > max) {
                max = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
        }
        return max;
    }



}
